public class Solution {
    public static void main(String[] args) {
        int[] arr = new int[]{9,8,7,6,5,4,3};
        shellSort(arr);
        for(int e: arr) {
            System.out.print(e + " ");
        }
    }

    public static void shellSort(int[] arr) {
        /**
         * 希尔排序
         *  此处枚举gap，gap初始设定arr.length,后续每次对半，直至gap=1*/
        int gap = arr.length / 2;
        while(gap >= 1) {
            sort(arr, gap);
            gap /= 2;
        }
    }

    public static void sort(int[] arr, int gap) {
        /**
         * 希尔排序*/
        // 1 预处理
        int n = arr.length;

        // 2 排序逻辑
        for(int i = 0; i < gap; i++) { // -外层循环枚举轮次
            // -内层循环（实现插入排序）
            for(int j = i+gap; j < n; j += gap) { // -中层遍历当前分组
                int temp = arr[j];
                int k = j-gap;
                while(k >= 0) { // -内层遍历为往前找位置
                    if(arr[k] > temp) {
                        arr[k + gap] = arr[k];
                        k -= gap;
                    } else {
                        break;
                    }
                }
                arr[k + gap] = temp;
            }
        }
    }

    public static void swap(int[] arr, int i, int j) {
        /**
         * 交换数组中两个元素的位置*/
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
